package Tree;

/**
 * 230.二叉搜索树中第K小的元素
 * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
 */
public class kthSmallest {
    /**
     * hot100一刷
     * hot100二刷
     */
    class Solution {
        int count = 0;

        public int kthSmallest(TreeNode root, int k) {
            if (root.left != null) {
                int l = kthSmallest(root.left, k);
                if (l != 0)
                    return l;
            }
            count++;
            if (k == count)
                return root.val;
            if (root.right != null) {
                int r = kthSmallest(root.right, k);
                if (r != 0)
                    return r;
            }
            return 0;
        }
    }
}
